package 算法.字符串.排序.键索引计数法;

import sun.rmi.runtime.Log;
import util.LogUtils;

/**
 * 【字符串排序：键索引计数法】
 * 
 * @Date 2017-09-09 16：35
 * @author Administrator
 * @version
 */
public class CountSort {

    public void indecCountIndex(int[] nums){
    	int SORT_COUNT = 4;						//共4种数字
    	int[] count = new int[SORT_COUNT+2];
    	
    	/**
    	 * 计算各元素频次，注：数组第0位不使用
    	 * 	eg： count[2] = 3;	//第2-1位元素(1)出现的次数为3
    	 */
    	for (int i = 0; i < nums.length; i ++)
    		count[nums[i]+1]++;
    	
    	/*
    	 * 将频次转换为各元素在排序后数组中的位置
    	 * 		对于每个键值i，小于i+1的键值之和为小于r的键值之和加上count[i]
    	 */
    	for (int i = 0; i < count.length-1; i ++)
    		count[i+1] = count[i+1] + count[i];
    	
    	for (int i = 0; i < count.length; i ++)
    		LogUtils.println("看下索引："+i, count[i]);
    	
    	int[] aux = new int[nums.length];
    	
    	/**
    	 * 排序
    	 */
    	for (int i = 0; i < nums.length; i ++) 
    		aux[count[nums[i]]++] = nums[i];
    	//遍历
    	for (int i = 0; i < aux.length; i ++) 
    		LogUtils.println("aux："+i, aux[i]);
    } 
    
    
    public static void  main(String[] args){
        int[] nums={2,3,4,1,2,4,3,1,2,2,1};
        CountSort sort=new CountSort();
        sort.indecCountIndex(nums);
    }
}
